package com.jxb.bit;

/**
 * 比特位计数
 *  * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，
 *  * 计算其二进制表示中 1 的个数 ，
 *  * 返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 * @author jiaobo
 * @date Created in 2024/12/24 21:38
 **/
public class CountingBits_338 {

    public static void main(String[] args) {
        System.out.println(2&1);
    }

    //x&=(X-1)：可以清除最低位的1
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for (int i = 1;i<=num;i++) {
            res[i] = res[(i-1)&i] + 1;
        }
        return res;
    }

    //奇偶性
    public int[] countBits1(int num) {
        int[] res = new int[num + 1];
        res[0] = 0;
        for (int i = 1;i<=num;i++) {
            //判断是否是奇数
            //奇数：上一个元素+1
            //偶数：i扩大2倍位置的元素
            res[i] = ((i&1) == 1 ? res[i-1] + 1 : res[i>>1]);
        }
        return res;
    }

}
